public class Sort {
    public static void main(String[] args) {
        Sort sort = new Sort();
        int[] arr = {5,2,3,1};
        sort.mergeSort(arr, 0, arr.length-1);
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public void insertSort(int[] array ){
        for(int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i;
            while( j > 0 && array[j-1] > tmp) {
                array[j] = array[j-1];
                j--;
            }
            array[j] = tmp;
        }
    }

    public void shellSort(int[] array) {
        for(int gap = array.length / 2; gap >= 1; gap /= 2) {
            shellSwap(array, gap);
        }
    }
    public void shellSwap(int[] array, int gap) {
        for(int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            while(j >= 0 && array[j] > tmp) {
                array[j+gap] = array[j];
                j -= gap;
            }
            array[j+gap] = tmp;
        }
    }

    public void selectSort(int[] array) {
        for(int i = 0; i < array.length; i++) {
            int minIndex = i;
            for(int j = i; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

    public void heapSort(int[] array) {
        createHeap(array);
        for(int i = 0; i < array.length; i++) {
            int tmp = array[0];
            array[0] = array[array.length-1-i];
            array[array.length-1-i] = tmp;
            shiftDown(array, 0, array.length-1-i);
        }
    }
    public void createHeap(int[] array) {
        for(int i = array.length / 2 - 1; i >= 0; i-- ) {
            shiftDown(array, i, array.length);
        }
    }
    public void shiftDown(int[] array, int root, int len) {
        int chile = root * 2 + 1;//左孩子节点
        if(chile >= len) {
            return;
        }

        if(chile+1 < len && array[chile] < array[chile+1]) {
            chile++;
        }

        if(array[chile] > array[root]) {
            swap(array, chile, root);
            shiftDown(array, chile, len);
        }
    }

    public void BubbleSort(int[] array) {
        for(int i = 0; i < array.length-1; i++) {
            for(int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array, j, j+1);
                }
            }
        }
    }

    public void quickSort(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }
        int div = partition(array, left, right);
        quickSort(array, left, div);
        quickSort(array, div+1, right);
    }


//    public int partition(int[] array, int left, int right) {
//        int pivot = array[left];
//        while(left <= right) {
//            while(left <= right && array[left] < pivot) {
//            }
//            while(left <= right && array[right] > pivot) {
//                right--;
//            }
//            if(left >= right) {
//                break;
//            }
//            swap(array, left++, right--);
//        }
//        return right;
//    }


    public int partition(int[] array, int left, int right) {
        int pivot = array[left];
        while (left < right) {
            while (left < right && array[right] >= pivot) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;
        return left;
    }

    public void mergeSort(int[] array, int left, int right) {
        if(left >= right) {
            return ;
        }
        int mid = left + (right - left) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        wayMerge(array,left, right);
    }

    public void wayMerge(int[] array, int left, int right) {
        int mid = left + (right - left) / 2;
        int i = left;
        int j = mid+1;
        int k = 0;
        int[] tmp = new int[right-left+1];
        while(k < tmp.length) {
            if(j > right || i <= mid && array[i] < array[j]) {
                tmp[k] = array[i++];
            }else{
                tmp[k] = array[j++];
            }
            k++;
        }
        k = 0;
        while(k < tmp.length) {
            array[left++] = tmp[k++];
        }
    }
}
